# 平衡二叉树: https://leetcode-cn.com/problems/balanced-binary-tree/submissions/

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 这些后序遍历的题，都是差不多的
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        """
            深度优先：后序遍历： 自底向上判断
        """
        flag = 1
        def postOrder(node):
            nonlocal flag
            if not node: return 0

            left = postOrder(node.left)
            right = postOrder(node.right)

            if abs(left - right) > 1:
                flag = 0

            # 左右子树的最大深度 + 1 等于当前树的深度
            return  max(left, right) + 1
        
        postOrder(root)

        return True if flag == 1 else False



# 还可以不必完全遍历，找到后直接回溯返回，不进行后序遍历了
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def height(root: TreeNode) -> int:
            if not root:
                return 0
            leftHeight = height(root.left)
            rightHeight = height(root.right)
            if leftHeight == -1 or rightHeight == -1 or abs(leftHeight - rightHeight) > 1:
                return -1
            else:
                return max(leftHeight, rightHeight) + 1

        return height(root) >= 0

